package 力扣_链表.面试常考;

/**
 * @author zx
 * @create 2022-08-30 14:27
 */
public class 合并K个升序链表 {
    /**
     * @return 归并分治
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        return mergeInternal(lists,0,lists.length - 1);
    }
    private ListNode mergeInternal(ListNode[] lists, int l, int r){
        if(r - l <= 0){
            return lists[l];
        }
        int mid = l + ((r - l) >> 1);
        ListNode l1 =  mergeInternal(lists,l,mid);
        ListNode l2 =  mergeInternal(lists,mid + 1,r);
        return merge(l1,l2);
    }
    private ListNode merge(ListNode list1, ListNode list2){
        ListNode dummyHead = new ListNode(10001);
        ListNode temp = dummyHead;

        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                temp.next = list1;
                list1 = list1.next;
            }else{
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        temp.next = list1 == null ? list2 : list1;
        return dummyHead.next;
    }

    /**
     * @return 暴力方法
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        ListNode res = null;
        for(int i = 0;i < lists.length;i++){
            res = mergeList2(res,lists[i]);
        }
        return res;
    }
    //合并链表
    private ListNode mergeList2(ListNode list1, ListNode list2){
        ListNode dummyHead = new ListNode(10001);
        ListNode temp = dummyHead;
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                temp.next = list1;
                list1 = list1.next;
            }else{
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        temp.next = list1 == null ? list2 : list1;
        return dummyHead.next;
    }
}
